import java.util.*;
 
public class Calc {

	public class State {
		public Stack<Double> stack = new Stack<Double>();
		public Stack<String> infix = new Stack<String>();
	}
	
	private State state;
	private String[] operators = {"+", "-", "*", "/", "^"}; // should in stack creation
	boolean isValid = true;

	
	public Calc() {
		state = new State();
	}
	
	private void initialize() {
		state = new State();
		isValid = true;
	}

	public String process(String expression) {
		
		double result = 0;
		initialize();
		
		for (String tok : expression.split(" ")) {
			if (isValid)
				processToken(tok);
			else
				return ("invalid expression");
		}
		
		if (!isValid)										/* last operation is invalid */
			return ("invalid expression");
		
		if (!state.stack.isEmpty()) {						/* get last variable */
			result = state.stack.pop();
		}
		
		if (!state.stack.isEmpty())							/* there are still numbers in the stack */
			return ("invalid expression");
		
		String infix = state.infix.pop();
		if (infix.startsWith("(") && infix.endsWith(")")) {
			infix = infix.substring(1,infix.length()-1);
		}
		
		return (infix + " = " + result);
	}
	
	/**
	 * 
	 * @param token
	 */
	void processToken(String token) {

		double rightNum, leftNum;

		if (token.length() > 0) {
			if (Character.isDigit(token.charAt(0))) {
				state.stack.push(Double.parseDouble(token));			/* add to calculation stack */
				state.infix.push(String.valueOf(Double.parseDouble(token)));	/* add to infix stack */
			}
			else { 
				if (Arrays.asList(operators).contains(token)) {
					
					try {
						rightNum = state.stack.pop();
						leftNum = state.stack.pop();
						
						state.stack.push(calculateExpression(leftNum, rightNum, token));
						
						String x2 = state.infix.pop(); /* elad will merge it with the second method */
						String x1 = state.infix.pop();
						addToInfix(x1, x2, token);
						
					} catch(Exception e) {
						isValid = false;
						return;
					}
				}
				else // invalid input
				{
					isValid = false;
				}
			}
		}
	}
	
	/**
	 * 
	 * @param num1
	 * @param num2
	 * @param token
	 * @return
	 */
	double calculateExpression(double num1, double num2, String token) {

		if (token.equals("+"))
		{
			return (num1 + num2);			
		}
		if (token.equals("-"))
		{
			return (num1 - num2);			
		}
		if (token.equals("*"))
		{
			return (num1 * num2);			
		}
		if (token.equals("/"))
		{
			return (num1 / num2);			
		}
		if (token.equals("^"))
		{
			return (java.lang.Math.pow(num1, num2));			
		}

		return -1.0;
	}
	
	/**
	 * 
	 * @param num1
	 * @param num2
	 * @param token
	 */
	void addToInfix(String num1, String num2, String token) {
		
		String exp;
		
		exp = "(" + num1 + token + num2 + ")";
		state.infix.push(exp);
		
	}
}
